/**
 * 912. 排序数组
 *
 * [中等]
 *
 * 给你一个整数数组 nums，请你将该数组升序排列。
 * 你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
 *
 * 示例 1：
 * 输入：nums = [5,2,3,1]
 * 输出：[1,2,3,5]
 *
 * 示例 2：
 * 输入：nums = [5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 */

export function sortArray(nums: number[]): number[] {
	return quickSort(nums)

	function quickSort(
		nums: number[],
		left: number = 0,
		right: number = nums.length - 1
	): number[] {
		const { length } = nums

		if (length > 1) {
			const lineIndex = findLineIndex(nums, left, right)

			if (left < lineIndex - 1) quickSort(nums, left, lineIndex - 1)

			if (lineIndex < right) quickSort(nums, lineIndex, right)
		}

		return nums
	}

	function findLineIndex(nums: number[], left: number, right: number): number {
		const midVal = nums[Math.floor(left + (right - left) / 2)]

		while (left <= right) {
			while (nums[left] < midVal) left++

			while (nums[right] > midVal) right--

			if (left <= right) {
				;[nums[left], nums[right]] = [nums[right], nums[left]]
				left++
				right--
			}
		}

		return left
	}
}
